#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa?tpId=49&&tqId=29370&rp=1&ru=/activity/oj&qru=/ta/2016test/question-ranking



struct ListNode* FindMiddle(struct ListNode* phead)
{
    struct ListNode* slow, * fast;
    slow = fast = phead;
    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

struct ListNode* ReverseList(struct ListNode* phead)
{
    if (phead == NULL)
        return NULL;
    struct ListNode* prev, * cur, * nex;
    prev = NULL;
    cur = phead;
    nex = cur->next;
    while (cur) {
        cur->next = prev;
        prev = cur;
        cur = nex;
        if (nex != NULL)
            nex = nex->next;
    }
    return prev;
}

class PalindromeList {
public:
    bool chkPalindrome(ListNode* head) {
        struct ListNode* mid = FindMiddle(head);
        struct ListNode* re = ReverseList(mid);
        struct ListNode* cur1, * cur2;
        cur1 = head;
        cur2 = re;
        while (cur1 && cur2)
        {
            if (cur1->val != cur2->val)
                return false;
            cur1 = cur1->next;
            cur2 = cur2->next;
        }
        return true;
    }
};